package guide.贪心算法;

import java.util.Arrays;

/**
 * <a href="https://leetcode-cn.com/problems/candy">135. 分发糖果</a>
 * 一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一
 * 个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所
 * 有孩子至少要有一个糖果。求解最少需要多少个糖果。
 * 示例 1：
 *  输入: [1,0,2]
 *  输出: 5
 *  题解：我们初始化糖果分配为 [1,1,1]，第一次遍历更新后的结果为 [1,1,2]，第二次遍历
 *  更新后的结果为 [2,1,2]。
 * @author 刘学松
 * @date 2021/2/15 17:27
 */
public class 分配糖果 {
    public static void main(String[] args) {
        int[] num = {1, 0, 2};
        System.out.println(candy(num));
    }

    public static int candy(int[] ratings) {
        int size = ratings.length;
        if (size < 2) {
            return size;
        }
        int[] num = new int[size];
        num[0] = 1;
        for (int i = 1; i < size; ++i) {
            if (ratings[i] > ratings[i-1]) {
                num[i] = num[i-1] + 1;
            } else {
                num[i] = 1;
            }
        }
        for (int i = size - 1; i > 0; --i) {
            if (ratings[i] < ratings[i-1]) {
                num[i-1] = Math.max(num[i-1], num[i] + 1);
            }
        }
        return Arrays.stream(num).sum();
    }
}
